#include<bits/stdc++.h>
#define int long long
#define For(i,a,b) for(int i=a;i<=b;++i)
#define Rof(i,a,b) for(int i=a;i>=b;--i)
#define rep(i,a) for(int i=1;i<=a;++i)
#define print(x) printf("%lld\n",(int)x)
#define prn(x) printf("%lld ",(int)x)
using namespace std;
const int N=2e6+5,Mod=1e9+7;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){f=(ch=='-'?-f:f);ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
int T;
int n,m;
map<pair<int,int>,int>mp;
vector<pair<int,int> > q[N];
int fa[N];
int find(int x){return fa[x]=(fa[x]==x?x:find(fa[x]));}
struct XXX{
int u,v,w;
}z[N];
inline bool cmp(XXX a,XXX b){
	return a.w<b.w;
}
int mx[N],len[N];
set<int>s[N];
int l[N],r[N];
signed main(){
	freopen("up.in","r",stdin);
	freopen("up.out","w",stdout);
	T=read();
	while(T--){
		n=read(),m=read();
		mp.clear();
		For(i,1,n)q[i].clear(),s[i].clear();
		For(i,1,n) s[i].insert(0),s[i].insert(n+1),l[i]=i-1,r[i]=i+1;
		For(i,1,m){
			int u=read(),v=read(),w=read();
			q[u].push_back({v,w});
			q[v].push_back({u,w});
			mp[{u,v}]=w;
			mp[{v,u}]=w;
			while(mp.count({u,l[u]}))l[u]--;
			while(mp.count({u,r[u]}))r[u]++;
			while(mp.count({v,l[v]}))l[v]--;
			while(mp.count({v,r[v]}))r[v]++;
		}
		if(n<=3000){
			int tot=0;
			For(i,1,n){
				For(j,i+1,n){
					if(mp.count({i,j})) z[++tot]={i,j,mp[{i,j}]};
					else z[++tot]={i,j,abs(i-j)};
				}
			}
			sort(z+1,z+tot+1,cmp);
			int ans=0;
			For(i,1,n) fa[i]=i;
			For(i,1,tot){
				if(find(z[i].u)!=find(z[i].v)){
					ans+=z[i].w;
					fa[find(z[i].v)]=z[i].u;
				}
			}
			printf("%lld\n",ans);
			continue;
		}
		z[0].w=1e16;
		int kuai=n,ans=0;
		For(i,1,n) fa[i]=i;
		For(t,1,2){
			For(i,1,n)mx[i]=0,len[i]=1e16;
			For(i,1,m){
				int u=z[i].u,v=z[i].v;
				if(mp[{u,mx[u]}]>z[i].w||!mp.count({u,mx[u]})){
					//~ cout<<1<<" ";
					if(find(u)!=find(v))mx[u]=v;
				}
				if(mp[{v,mx[v]}]>z[i].w||!mp.count({v,mx[v]}))mx[v]=u;
			}
			For(i,1,n){
				if(!l[i]&&!r[i]) continue;
				if(!l[i]||(abs(r[i]-i)<abs(l[i]-i)&&r[i]!=n+1)){
					if((mp[{i,mx[i]}]>abs(r[i]-i))||(!mp.count({i,mx[i]}))){
						if(find(i)!=find(r[i]))mx[i]=r[i];
					}
				} 
				else{
					if(mp[{i,mx[i]}]>abs(l[i]-i)||!mp.count({i,mx[i]})){
						if(find(i)!=find(l[i]))mx[i]=l[i];
					}
				} 
			}
			//~ For(i,1,n){
				//~ cout<<mx[i]<<" ";
			//~ }
			For(i,1,n){
				int w1=(mp.count({i,mx[i]})?mp[{i,mx[i]}]:abs(i-mx[i]));
				if(w1<len[find(i)]){
					len[find(i)]=w1;
					mx[find(i)]=mx[i];
				}
			}
			//~ puts("");
			For(i,1,n){
				if(find(i)!=i)continue;
				int w=len[i];
				fa[find(mx[i])]=i;ans+=w;
				kuai--;
			}
			if(kuai==1) break;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
//
